2020-05-22 18:29:00

/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     public $val = null;
 *     public $left = null;
 *     public $right = null;
 *     function __construct($value) { $this->val = $value; }
 * }
 */
class Solution {

    /**
     * @param Integer[] $inorder
     * @param Integer[] $postorder
     * @return TreeNode
     */
    function buildTree($inorder, $postorder) {
        $treeRoot = new TreeNode(null);
        $this->loop($treeRoot, $inorder, $postorder);
        return $treeRoot;
    }
    function loop($tree, $inorder, $postorder){
        $tree->val = $postorder[count($postorder) - 1];
        if(1 >= count($inorder)){
            return $tree;
        }
        $leftLen = array_search($tree->val, $inorder);
        //中序遍历 左
        $inorderLeft = array_slice($inorder, 0, $leftLen);
        //后序遍历 左
        $postorderLeft = array_slice($postorder, 0, $leftLen);;
        //中序遍历 右
        $inorderRight = array_slice($inorder, $leftLen + 1);
        //后序遍历 右
        $postorderRight = array_slice($postorder, $leftLen, -1);
        if(!empty($postorderLeft)){
            $treeLeft = new TreeNode(null);
            $tree->left = $this->loop($treeLeft, $inorderLeft, $postorderLeft);
        }
        if(!empty($postorderRight)){
            $treeRight = new TreeNode(null);
            $tree->right = $this->loop($treeRight, $inorderRight, $postorderRight);
        }
        return $tree;
    }
}